package leetcode.editor.cn;

import java.util.Arrays;

/**
 * 最长递增子序列
 * @author qulq
 * @date 2024-07-28 09:12:27
 */
public class T300_LongestIncreasingSubsequence{
	 public static void main(String[] args) {
	 	 // 测试代码
		 Solution solution = new T300_LongestIncreasingSubsequence().new Solution();
		 System.out.println(solution.lengthOfLIS(new int[]{1, 3, 6, 7, 9, 4, 10, 5, 6}));
	 }

	/**
	 * f[i]【前】i个中，最长子序列
	 * f[i] = max(f[j] +1) 1 <= j < i
	 */
// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int lengthOfLIS(int[] nums) {
		if (nums.length == 1) {
			return 1;
		}
		int[] dp = new int[nums.length + 1];
		Arrays.fill(dp, 1);
		int ans = 1;
		for (int i = 2; i <= nums.length; i++) {
			for (int j = 1; j < i; j++) {
				if (nums[j - 1] < nums[i - 1]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
					ans = Math.max(ans, dp[i]);
				}
			}
		}
		return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}